package com.剑指offer.第八章树;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 前序遍历 第二个循环 一直往下一边遍历左节点一边记录当前的节点的值
 * 另外两个中序遍历、后序遍历 都是先将左节点放入到栈中
 */
public class 二叉树的深度优先搜索 {

    /**
     * 中序遍历
     * 则先遍历二叉树的左子树，然后遍历二叉树的根节点，最后遍历二叉树的右子树
     * 1
     * 2    3
     * 4   5 6  7
     * <p>
     * <p>
     * 结果为：4 2 5 1 6 3 7
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> lists = new ArrayList<>();
        dfs(root, lists);
        return lists;
    }

    public void dfs(TreeNode root, List<Integer> nodes) {
        if (root != null) {
            dfs(root.left, nodes);
            nodes.add(root.val);
            dfs(root.right, nodes);
        }
    }

    /**
     * 使用单调栈
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversalOfStack(TreeNode root) {
        List<Integer> nodes = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            // 顺着指向子节点的指针一直向下移动，循环之后 最左子节点位于栈顶
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 取出栈顶
            cur = stack.pop();
            nodes.add(cur.val);
            cur = cur.right;
        }
        return nodes;
    }


    /**
     * 前序遍历
     * 1 2 4 5 3 6 7
     *
     * @param root
     * @param nodes
     */
    public void preorderDfs(TreeNode root, List<Integer> nodes) {
        if (root != null) {
            nodes.add(root.val);
            dfs(root.left, nodes);
            dfs(root.right, nodes);
        }
    }

    public List<Integer> preorderTraversalOfStack(TreeNode root) {
        List<Integer> nodes = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                nodes.add(cur.val);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return nodes;
    }


    /**
     * 后置遍历
     * 4 5 2 6 7 1
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversalDfs(TreeNode root) {
        List<Integer> nodes = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null; // 记录前一个右节点

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                // 先将左节点放入到栈中
                cur = cur.left;
            }

            cur = stack.peek();
            if (cur.right != null && cur.right != pre) {
                cur = cur.right;
            } else {
                stack.pop();
                nodes.add(cur.val);
                pre = cur;
                // 下一个需要遍历的节点是父节点，已经存在了，所以重置为null
                cur = null;
            }
        }
        return nodes;
    }

}
